package com.dycong.common.leetcode.yi;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yilin
 * Date: 2019-07-16
 * Time: 15:44
 */
public class SortList {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(4);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(1);
        l1.next.next.next = new ListNode(3);
        ListNode result = sortList(l1);
        while (result != null) {
            System.out.print(result.val + "\t");
            result = result.next;
        }
    }


    //归并排序：先拆分到最小元素(比如只有两个值)，然后做合并排序
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode slow = head;
        ListNode first = head;
        while (first != null && first.next != null) {
            pre = slow;
            slow = slow.next;
            first = first.next.next;
        }

        pre.next = null;//断掉链接
        //最递归拆分
        ListNode left = sortList(head);
        ListNode right = sortList(slow);

        return merge(left, right);

    }

    private static ListNode merge(ListNode left, ListNode right) {
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else if (left.val < right.val) {
            left.next = merge(left.next, right);
            return left;
        } else {

            right.next = merge(right.next, left);
            return right;
        }

    }

//    public static ListNode sortList(ListNode head) {
//        if(head==null || head.next==null) return head;
//        ListNode slow=head,fast=head,pre=null;
//        while (fast!=null && fast.next!=null){
//            pre=slow;
//            slow=slow.next;
//            fast=fast.next.next;
//        }
//        pre.next=null;
//        ListNode left=sortList(head);
//        ListNode right=sortList(slow);
//        return  merge(left,right);
//
//    }
//
//    private static ListNode merge(ListNode left, ListNode right) {
//        if(left==null){
//            return right;
//        }else if(right==null){
//            return left;
//        }else if(left.val<right.val){
//            left.next=merge(left.next,right);
//            return left;
//        }else {
//            right.next=merge(left,right.next);
//            return right;
//        }
//    }

}
